﻿//1130. 叶值的最小代价生成树
//给你一个正整数数组 arr，考虑所有满足以下条件的二叉树：
//每个节点都有 0 个或是 2 个子节点。
//数组 arr 中的值与树的中序遍历中每个叶节点的值一一对应。
//每个非叶节点的值等于其左子树和右子树中叶节点的最大值的乘积。
//在所有这样的二叉树中，返回每个非叶节点的值的最小可能总和。这个和的值是一个 32 位整数。
//如果一个节点有 0 个子节点，那么该节点为叶节点。


class Solution {
public:
    int mctFromLeafValues(vector<int>& arr)
    {
        int res = 0;
        stack<int> sta;
        for (auto x : arr)
        {
            while (sta.size() && x >= sta.top())
            {
                int y = sta.top();
                sta.pop();
                if (sta.empty() || sta.top() >= x)
                {
                    res += y * x;
                }
                else
                {
                    res += sta.top() * y;
                }
            }
            sta.push(x);
        }
        //单调递减
        while (sta.size() >= 2)
        {
            int x = sta.top();
            sta.pop();
            res += sta.top() * x;
        }
        return res;
    }
};